#include <vector>
#include <math.h>

using namespace std;

struct location 
{
	int ts;
	int x;
	int y;
};

namespace ksp
{
	class KSP
	{
	private:
		int pom_locations, total_locations, max_detections, pom_x, pom_y, begin_frame, 
			num_of_frames, batch_size, num_of_batches, vsource, vsink;
		double pass_prob;
		bool first_graph;
		vector<vector<double>> node_prob;

		location intToLocation( int loc );

		int locationToInt( location l );
		
		void combinePaths( vector<vector<int>> partialPaths, vector<vector<location>> & completePaths, 
			int lastTimeStep ) ;
	public:
		KSP( vector<vector<double>> node_prob_, int pom_x_, int pom_y_, double pass_prob_, int begin_frame_,
			int num_of_frames_, int batch_size_ )
		{
			max_detections = 25;
			first_graph = true;
			pom_x = pom_x_;
			pom_y = pom_y_;
			pom_locations = pom_x * pom_y;
			total_locations = pom_locations * num_of_frames_ + 2; // +2 because of vsource and vsink nodes
			pass_prob = pass_prob_;
			begin_frame = begin_frame_;
			num_of_frames = num_of_frames_;
			batch_size = batch_size_;
			num_of_batches = int(ceil((double(num_of_frames)/double(batch_size))));
			node_prob = node_prob_;
			vsource = 0;
			vsink = total_locations - 1;
		};

		void findKSP( vector<vector<location>> & paths_all );
	};
}